from python算法.Graph.Ljt import graph
from collections import defaultdict
class solution():
    def __init__(self,file=None):
        self.__preorder = []
        self.__postorder = []
        self.cg = graph(file)
        self.G = self.cg.readGraph()
        self.V  = self.cg.getV
        self.E = self.cg.getE
        self.__visited = [-1]*self.V#用来记录多个联通分量的首个Node或者可以说记录图中的节点是否被访问
        self.__Cpnumber = 0#图的连通数量的个数
        self.__raodpath = [-1]*self.V


    def GetCpNumber(self):
        return self.__Cpnumber

    def LtFlInfo(self):
        self.ltflinfo = defaultdict(list)
        self.GetPreDfsOrder()
        for node,val in enumerate(self.__visited):
             self.ltflinfo[val].append(node)
        return self.ltflinfo

    def GetPreDfsOrder(self):
        for i in range(self.V):
            if self.__visited[i]==-1:
                self.__dfs(i,self.__Cpnumber)#一个节点得到一个联通分量
                self.__Cpnumber+=1
        return self.__preorder

    def GetPostDfsOrder(self):
        for i in range(self.V):
            if not self.__visited[i]:
                self.__dfs(i)#一个节点得到一个联通分量
        return self.__postorder

    def __dfs(self,v,nodeid):
        self.__preorder.append(v)
        self.__visited[v] = nodeid
        for i in self.cg.adjacentVertices(v):
            if  self.__visited[i]==-1:
                self.__dfs(i,nodeid)
        self.__postorder.append(v)
if __name__ == '__main__':
    s = solution(r"D:\tensorflow2_pytorch\python算法\Graph\ltflbl.txt")
    print("图的先序优先遍历：",s.GetPreDfsOrder())

